package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 让字符串成为回文的最少插入次数
    static class Solution {
        public int minInsertions(String s) {
            char[] ch = s.toCharArray();
            int n = ch.length;
            int[][] dp = new int[n][n];

            // 1) 从后往前遍历 i，从 i 开始往后遍历 j
            for (int i = n - 1; i >= 0; i--) {
                for (int j = i; j < n; j++) {
                    if (ch[i] == ch[j]) {
                        // 2) 两端字符相同：已经是回文，不需要插入
                        if (i == j) {
                            dp[i][j] = 0;  // 单个字符
                        } else if (i + 1 == j) {
                            dp[i][j] = 0;  // 两个相同字符
                        } else {
                            dp[i][j] = dp[i + 1][j - 1];  // 中间部分需要的插入次数
                        }
                    } else {
                        // 3) 两端字符不同：在左边插入 ch[j] 或在右边插入 ch[i]，取较小值
                        dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
                    }
                }
            }
            // 4) dp[0][n-1] 就是整个字符串变成回文需要的最少插入次数
            return dp[0][n - 1];
        }
    }
}
